Address translation is the process of mapping an address, such as the network address contained in a packet, to some desired information. Examples of desired information include determining the output port of a switch to which a packet should be sent, or determining the address of the next-hop router for the routing of IP (Internet Protocol) datagrams. Address filtering is similar to address translation, except that instead of finding the data associated with some address, it is only important to determine whether a given address exists in a table of addresses. Throughout this disclosure, the phrase "address translation" encompasses both address translation and address filtering.
Addresses can be placed into two categories with regard to processing: flat and hierarchical. Flat addresses are those addresses that have no internal structure that is useful from a processing aspect. Ethernet addresses are an example of a flat address. Although Ethernet addresses have some structure to them (e.g., one part of the Ethernet address denotes the manufacturer of the equipment using the given Ethernet address), the structure is not relevant to protocol processing operations, such as routing. Many techniques have been developed for accelerating flat address translation.
Hierarchical addresses are those addresses that have an internal structure that is useful for protocol processing. Examples of hierarchical addresses include IPv4 addresses, IPv6 addresses, E.164 addresses (used in ATM-asynchronous transfer mode), and telephone numbers. To better illustrate the internal structure of a hierarchical address, a telephone number is used . Consider a telephone number: (908) 979-1010. The highest level of the hierarchy is denoted by the "area code" 908. The next level of the hierarchy is the "central office code" 979. The lowest level of the hierarchy is the "station number" 1010. The hierarchical structure of the telephone number is used to determine how to route a call through the telephone network. For example, if a call both originates and terminates in the 979 central office, then the phone call passes only through the 979 central office. If a call both originates and terminates in the 908 area, then no long-distance carrier is used to carry the call. Note that a flat address is a hierarchical address with a single level of hierarchy. Thus, any address translation techniques that operate on hierarchical address can be applied to flat addresses as well.
The main importance of the structure of hierarchical addresses is that there is no need to store information about every single address in order to be able to process all addresses. Information about entire classes of addresses can be stored in a single entry. For example, for a call that originates from area code 908 and terminates in some other area code, the correct action is to forward the call to a long distance carrier, regardless of the specific terminating area code.
The tables used for hierarchical address translation can be thought of as a sieve. Consider the following example, as shown in FIG. 1, of a translation table that might exist in the 979 central office switch (X's represent "wildcard" or "don't care" values that match all digits). Telephone numbers are compared with table entries in order from top to bottom looking for a matching entry. The telephone number 908 979 1035 would match entry A in the table, and the call would be routed to the station number 1035. The telephone number 201 829 5136 matches entry D of the table and would be routed to a long distance carrier for transport. Note that any telephone number that matches an entry also may match some of the entries that follow. The fact that entries are examined in order assures that routine is done correctly.
Other methods can be used to search the table that will provide the same result as if the table were searched serially. One technique is to use a tree structure, such as a PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric) tree. The Art of Computer Programming (Knuth), Introduction to Algorithms (Cormen, Leiserson, and Rivest). The search begins at the root of the tree, which corresponds to the top of the hierarchy. FIG. 2 depicts such a search method and comprises the table of FIG. 1 re-arranged as shown in FIG. 2. The first comparison would be against just the area code 908. If 908 were found, then the entries indented under 908 would be searched. Otherwise, the call will match the last line and be routed to a long distance Point-of-Presence.
Another alternative would be to search all entries in parallel. As shown in FIG. 3, the table can be augmented with explicit hierarchical levels assigned to each table entry. The telephone number 908 979 1035 matches table entries A, C and D. The desired match is entry A, which has the highest level number (3 in this case, i.e., only two entries need to be delineated A & B. The word "address" as used above may actually be a combination of data fields from a packet header that is treated as a single address for purposes of address translation. For example, the address may be a combination of source address, destination address and priority fields. It should be noted that any combination of different header elements forms a single hierarchical address, in which the different elements form part of the structure of the hierarchical address.
However, these approaches are limited by the constraints of software processing speeds and comparisons with table entries are typically performed in sequential order. Thus, as network communication speeds increase, it becomes necessary to find high-speed translation techniques to operate at wirespeed.
One way to achieve wirespeed is to utilize a content-addressable memory (CAM). CAMs differ from conventional RAM (random access memory), SRAM (static RAM) and DRAM (dynamic RAM) in that they are organized differently. In a CAM, data is stored in locations in an arbitrary fashion. The locations can be selected by an address bus, or the data can be written directly into the first empty location because every location has a special status bit that keeps track of whether the location has valid information in it or is empty and available for overwriting. Once information is stored in a memory location, it is found by comparing every bit in memory with data placed in a special Comparand register. CAMs also comprise a mask register which allows selection of which bits will participate in the comparison. If there is a match for every bit in a location with every corresponding bit in the Comparand register, a Match Flag is asserted to the user know that the data in the Comparand register was found in memory. A priority encoder sorts out which matching location has the top priority, if there is more than one, and makes the address of the matching location available to the user. Thus, a CAM is a memory device that allows retrieval of information by specifying part of the stored information, rather than by specifying a storage address. For example, using masking, if the entries hex "abcd," "abde" and "accd" were stored in a CAM, the CAM could be instructed to return the complete contents of the entries of all locations beginning "ab." In this example, the CAM would return entries "abcd" and "abde."
CAMs are generally classified as either binary or ternary CAMs. Binary CAMs store binary entries, while ternary CAMs store ternary entries (see PCT Application No. PCT/US97/13216, WO98/07160). Binary entries are entries that contain only 0 or 1 values, while ternary entries are entries that contain 0, 1, or X (i.e., "don't care") values. Note that a single ternary entry can be expressed as two or more binary entries. In other words, a single ternary entry "1X0" can be represented by two binary entries "110" or "100", or a single ternary entry "1XX" can be represented by four binary entries "100", "101", "110" or "111", etc. Since hierarchical addresses often comprise ternary values (e.g., a telephone lookup table number "908-979-XXXX", ternary CAMs require a smaller number of table entries to represent each hierarchical address than binary CAMs. However, ternary CAMs require more complex hardware and are generally more expensive than binary CAMs. (see U.S. Pat. No. 5,319,590 (Montoye)). In particular, one method to construct a ternary CAM is to design the CAM cells and sense amps to enable the storage of three distinct voltage levels (high, medium and low) which would correspond to the ternary values.
The following provides a summary of existing searching methods using CAMs.
Expanding Each Ternary Entry Into Multiple Binary Entries
While hierarchical addresses can be directly stored in ternary CAMs, in order to be stored in binary CAMs they must first be translated into binary format. As discussed above, a ternary address can be translated into two or more binary addresses. However, the number of binary addresses needed to represent a ternary address is 2.sup.m, where m is the number of bits required to represent each "don't care" value (X) in the ternary address. For example, the ternary address ABCD.sub.-- 123X.sub.hex, where "X" indicates the "don't care" value, covers the set of binary addresses given by {ABCD.sub.-- 1230.sub.hex ;ABCD.sup.-- 1231.sub.hex ; . . . ABCD.sub.-- 123F.sub.hex } where m=4 to cover the range 0 to F. Hence, the ternary address ABCD.sub.-- 123X.sub.hex requires 16 (i.e., 2.sup.4) entries in the binary CAM. To that end, in accordance with application Ser. No. 08/818,073, filed on Mar. 14, 1997, entitled "Accelerated Hierarchical Address Filtering and Translation," which is assigned to the same assignee as the present invention, namely, Music Semiconductors, Inc., and all of whose disclosure is incorporated by reference herein, there is disclosed a method for storing such entries in a binary CAM acting as a ternary CAM but not having to store these entries in sequential order.
Hierarchical Level Field Searches
Another search technique involves the use of entries in a ternary CAM with a hierarchical level field, using a linear search of this level field. Fast Routing Table Lookup Using CAMs, (McAuley and Francis, 1993). In particular, this technique uses a ternary CAM to store ternary addresses and wherein each ternary address comprises an associated level field. The entries may be stored in the CAM in any order. The following is an example of how an address and mask are stored. The ternary address, ABCD.sub.-- 123X.sub.hex /28 (where "28" indicates the number of contiguous ones in the mask), would be stored in the CAM as: EQU ternary field=ABCD.sub.-- 123X.sub.hex EQU priority field=11100.sub.binary (where 11100.sub.binary =28.sub.decimal)
The technique then begins searching from the lowest priority level (i.e., the level with the longest network mask, viz., 11111.sub.binary) and working towards the higher levels, depending upon whether there are any matches. The search is altered based on the level field. The hierarchical address is not masked during the search and only parts of the level field are masked. If a match is found, the search is complete; if there are no matches, the level field is decremented and the search continues. The worst case number of searches is the number of distinct hierarchical levels, N.
Entries in Ternary CAMs with Hierarchical Level Field, Binary Search of Level Field
Another technique, that is an improvement of the Hierarchical Level Field Searches, (described above), is disclosed in application Ser. No. 08/818,073, filed on Mar. 14, 1997, entitled "Accelerated Hierarchical Address Filtering and Translation", which is also assigned to the same assignee as the present invention, namely, Music Semiconductors, Inc., and all of whose disclosure is incorporated by reference herein. In this technique, instead of starting at the lowest level of the hierarchy (comprising N hierarchical levels) and working up (i.e., Hierarchical Level Field Searches), this search technique starts in the middle and eliminates from consideration one half of the remaining hierarchical levels during each iteration. In particular, the search starts in the middle mask (i.e., MM=N/2) and, as an example, N=32. Depending upon the search result, the search either moves up or down MM/2 mask levels and tries again. The search begins looking for matches with the level field 1XXX, which will match against priority levels 16-31 since:
16.sub.decimal =10000 PA1 17.sub.decimal =10001 PA1 24.sub.decimal =11000 PA1 31.sub.decimal =11111 PA1 0.sub.decimal =00000 PA1 1.sub.decimal =00001 PA1 8.sub.decimal =01000 PA1 15.sub.decimal =01111
If there are multiple matches in this range (16-31), the mask is changed to 11XXX (i.e., replace the most significant X of the priority mask with a "1"). By doing so, the search range is halved, resulting in a new smaller range, viz., 24-31. After searching with the new mask, if there is one match, the search is complete; if there is no match, the least significant 1 of the priority mask is replaced with a 0 (i.e., the new mask is now 10XXX) so that the range of 16-23 is now searched.
If, on the other hand, there are no matches in this range (16-31) when the original mask 1XXX was used, the mask is changed to 0XXX which means that the search is now looking at the range 0-15 of the priority masks, since:
After searching with the new mask, if there is one match, the search is complete; otherwise, the search process is repeated by replacing the most significant X with a 1 (i.e., 01XX, searching the range 8-15). If there is no match, the least significant 1 is replaced with a 0 (i.e., 00XX, searching the range 0-14) and the process repeated until a match is found.
This technique is depicted in FIG. 4 and can be summarized as follows: The ternary CAM is first searched for an address and a priority field having a 1 in the most significant bit position and an X in all other bit positions, in stage 2. Stage 4 then determines if there are any matching entries, in which case, the operation proceeds to stage 8; otherwise, the least significant bit in the priority field having a value of 1 is replaced by a value of 0 in stage 6. Stage 8 then determines whether any bits of the priority field have a value of X, in which case, the most significant bit in the priority field having a value of X is replaced by a value of 1 in stage 10. The CAM is then searched for the address and the modified priority field, in stage 12. Stage 14 determines whether there is a single matching entry, in which case, the matching entry is retrieved from the CAM in stage 16; otherwise, stages 4-14 are repeated until the test of stage 14 is satisfied and the operation terminates. Thus, one X is resolved (i.e., replaced by a 1 or a 0) after each search until a matching entry is found.
This technique requires, in the worst case, a number of searches equal to the number of bits used to represent the priority field (i.e., if N is the number of hierarchical levels represented by the priority field, log.sub.2 N searches are required to find a matching entry at the lowest hierarchical level, as all bits of the priority mask must be resolved).
Full-Sorted Order with Different Masks
Another technique disclosed in Fast Routing Table Lookup Using CAMs, (McAuley and Francis, 1993) comprises the storage of entries in full-sorted order in a binary CAM with linear searching of the hierarchy using different mask registers. Binary entries are stored in a binary CAM and the CAM entries must be ordered inversely by level of hierarchy. Instead of using priority masks, this technique masks off the address being searched in a manner similar to how the priority masks are decremented, as described above under "Hierarchical Level Field Searches". In particular, this technique (shown in FIG. 5) starts with the most precise mask of all "care" bits in the mask register and searches the CAM through the mask register. For example, for a 32-bit address search, the technique would begin with all "0's" in the mask register (a/32 mask), where "0" s correspond to "care" and "1"s correspond to "don't cares" in a CAM search through a mask. If there is a match, the search is completed and the top CAM match (i.e., the lowest CAM address) is selected. If there is no match, the technique moves down to the next highest mask value, which is /31 in this case. The search is repeated again through the mask register, repeating the process until a single match is received. The worst case number of searches is N searches, where N is the number of hierarchical levels.
Entries in Full-Sorted Order in Binary CAM with Binary Search of Hierarchy Using Different Mask Registers
This technique, as disclosed in application Ser. No. 08/818,073, filed on Mar. 14, 1998, entitled "Accelerated Hierarchical Address Filtering and Translation", is an improvement to Full-Sorted Order with Different Masks (discussed above) by providing a search to log.sub.2 N. This technique also starts with the median, or half-way mask, which would be the /16 mask in a 32 mask level address scheme. If there is a single match, the search is complete. If there are multiple matches, the search moves to the mask half-way up, which is the /24 mask in this iteration and the search continues. If there are still no matches, the search moves the other way and half-way down, i.e., to the /8 mask in this iteration and the search continues. This process is repeated until one match is found or until no matches are found, in which case the highest priority match from the last multiple match search is selected.
Full-Sorted Order
This technique is disclosed by Fast Routing Table Lookup Using CAMs, (McAuley and Francis, 1993) and is shown in FIG. 6. In this technique, ternary entries are stored in sorted, i.e., inverse hierarchical, order. A search takes a single cycle because the search obtains the longest match address which is stored at the lowest CAM address. The major advantage of this approach is the ideal one search cycle address resolution time. On the other hand, the downside of this technique is the required resorting which makes this technique impractical.
IP Classless Inter Domain Routing (CIDR)
The present invention can be implemented in any type of communication system where hierarchical addressing and associated address masks are used. As an example, as will be disclosed below, the present invention can operate on the IP Classless Inter Domain Routing (CIDR) to find the "longest match" in an IP routing table. CIDR is a common method of reducing address table size, which categorizes address aggregations on arbitrary mask bit boundaries. CIDR reduces the size of IP tables by making it possible to group thousands of entries under one entry in the CIDR table. FIG. 7 shows two examples of how the 32-bit network mask values are structured according to Internet Request For Comments 940 and 1519. The masks always have a structure consisting of contiguous "0"s on the right. A mask never has "1"s and "0"s interleaved, or "0"s on the left and "1"s on the right. FIG. 8 shows examples of invalid mask structures.
FIG. 9 shows four entries from a CIDR routing table (in hexadecimal format) and the network masks that relate to them. It can be seen that the mask boundaries are clearly demarcated. The number after the backslash indicates the number of continuous ones in the mask. For example, the first entry's mask is FF.FF.FF.FF, which corresponds to 32 bits set to 1. This mask is an IP mask, where a 1 indicates a "care" location and a 0 indicates a "don't care." A "care" bit means that the corresponding bit locations of the numbers being compared must be identical. A "don't care" bit indicates that the bit locations are not used in the comparison. The more the number of 1-bits or "cares" in a mask, the less the number of possible matches. Therefore, a higher mask number is more precise that a lower mask number. Note, an IP address search may match multiple CIDR routing table entries because masking is used to further specify smaller address ranges.
In FIG. 9, the last address/mask entry actually corresponds to 1100 0000 0001 1000 XXXX XXXX XXXX XXXX where the X's stand for "don't cares." Any search value whose top 16 bits equal 1100 0000 0001 1000 would match the last entry. Note that in FIG. 9, the entries are ordered by mask value from most 1s (FF.FF.FF.FF) to the entry with the least number of 1s (FF.FF.00.00, in this case). A search for C0.18.0C. 15 would yield matches on all the entries but the first entry is chosen because it is the match with the longest group of 1s in the mask (the so-called "longest match"). A search for C0.18.0C.16 would match only the second, third, and fourth entries.
When multiple matches occur during a search, CAMs select the "best" entry by their physical addresses. Matches with lower addresses are selected over matches with higher addresses. For example, if a search yields matches at CAM address 1 and 2, the match at address 1 is selected. In a typical layer 2 address filtering application, the order of the entries in the CAM is unimportant because it is expected that there will be no more than one match result from any given search.
However, hierarchical address structures like IPv4, IPv4 CIDR, and IPv6 differ by having the possibility of having multiple matches during a search operation. The best match is the "longest match," or the entry has the largest number of contiguous "cares" or 1s. Therefore, if a CAM is used to store hierarchical addresses, sorting is necessary. There are two alternatives for this sorting- sorting when inserting entries, or sorting when reading matches. Fast hardware lookup for high bandwidth routing and switching places an emphasis on high-speed searches. Choosing to sort when inserting entries is therefore a logical decision because it enables fast constant time address resolution.
Thus, as network communication speeds increase, there remains a need to conduct hierarchical address translation at wirespeed, rather than relying on software techniques as is practiced in conventional translation techniques, or on present CAM techniques. In particular, there remains a need for a method of sorting entries in the CAM to obtain the longest match in the shortest amount of time.